#include "input.h"
#include "output.h"
#include "binary_heap.h"
#include "btree.h"
#include "compress.h"
#include <stdlib.h>
char *codes[ANSI_COUNT];
char code[ANSI_COUNT] = "";

/**
 * Generates the code by traversing the code tree.
 * The function is called recursively to build up the code until the leafes
 * are reached, meaning we got the complete code for the symbol stored in this
 * leaf.
 *
 * @param node - The node form which we start to go through the tree.
 */
static void generate_codes(BTREE_NODE *node);

extern char **get_encoding(int occurrence[])
{
    int i;
    BTREE* min_1;
    BTREE* min_2;
    BTREE_NODE *root_node;

    /* initialize heap */
    heap_init();

    /* construct optimal code tree */
    for (i = 0; i < ANSI_COUNT; ++i)
    {
        if (occurrence[i] > 0)
        {
            BTREE* new_btree = btree_new(i, NULL, NULL, occurrence[i]);
            heap_insert(new_btree);
/*
            heap_print();
*/
        }
    }

    while (heap_extract_min(&min_1) &&
            heap_extract_min(&min_2))
    {
        heap_insert(btree_merge(min_1, min_2, NULL));
    }

    root_node = btree_get_root(min_1);
/*
    btree_print(min_1);
*/
    generate_codes(root_node);

    return codes;
}

static void generate_codes(BTREE_NODE *node)
{
    char *code_copy;
    if (!node)
    {
        return;
    }
    if (btreenode_is_leaf(node))
    {
        /* This code works by some delicate magic */
        code_copy = malloc(sizeof(code));
        strcpy(code_copy, code);
/*
        printf("node %x leaf! char: %d, code is: %s\n", node, node->value, code);
*/
        codes[node->value] = code_copy;
    }
    else
    {
        strcat(code, "0");
        generate_codes(btreenode_get_left(node));
        code[strlen(code) - 1] = 0;
        strcat(code, "1");
        generate_codes(btreenode_get_right(node));
        code[strlen(code) - 1] = 0;
    }
}
